package algorithm.sort;

import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2021/1/1 14:14
 * @Version 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        //1.构建大顶堆
        //i从所有的非叶子节点开始
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子节点从下到上，从左到右调整结构
            adjustHeap(arr, i, arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);//将堆顶元素与堆的末尾元素进行交换
            //再重新调整结构
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调整大顶堆
     * @param arr 待排序的数组
     * @param i   当前堆顶元素所在的索引
     * @param length 当前堆的长度
     */
    public static void adjustHeap(int[] arr, int i, int length){
        int temp = arr[i];
        //从当前堆顶元素的左子节点开始找
        for (int j = 2 * i + 1; j < length; j = j * 2 + 1) {
            //如果左子节点小于右子节点
            if (j + 1 < length && arr[j] < arr[j + 1]) {
                j++;
            }
            //如果子结点大于最初的那个父节点，就将子结点的值赋值给父节点
            //并将i移到末尾
            if (arr[j] > temp) {
                arr[i] = arr[j];
                i = j;
            } else {
                break;
            }
        }
        //将temp的值放在该子二叉树的末尾位置
        arr[i] = temp;
    }

    /**
     * 交换元素
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


}
